package com.example.demo.leetcode.top100;

import java.util.LinkedList;
import java.util.List;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _61分割回文串
 * @description
 * @date 2023/06/22 14:29
 * <p>
 * ******************************************************
 */
public class _61分割回文串 {

    List<List<String>> result = new LinkedList<>();
    LinkedList<String> trace = new LinkedList<>();

    public List<List<String>> partition(String s) {

        backtrack(s.toCharArray(), 0);
        return result;
    }

    private void backtrack(char[] charArray, int i) {
        if (i == charArray.length) {
            result.add(new LinkedList<>(trace));
            return;
        }

        for (int j = i; j < charArray.length; j++) {
            if (!checkPalindrome(charArray, i, j)) {
                continue;
            }
            trace.addLast(new String(charArray, i, j + 1 - i));
            backtrack(charArray, j + 1);
            trace.removeLast();
        }
    }


    private boolean checkPalindrome(char[] charArray, int left, int right) {
        while (left < right) {
            if (charArray[left] != charArray[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
